Thread: Substring Problem | Optimization needed

I need some help in solving this substring problem am dealing with, here's the problem:

Q:
Find the longest substring in a string(that we input) that contains at least one character who's frequency is greater than or equal to the (length of that substring)/2..

constraint:

1<=n<=10⁵ (length of string inputted)

input:
2
5
abcde
14
ababbbacbcbcca

output:
3
13

Sample test case 2: We can select the substring starting from index 1 to 13, here the frequency of b is 6 which is greater than or equal to 13/2=6(take floor value).

Note that, there can be multiple possible substrings.

My approach:

I already tried the brute force method, but that is not very efficient way of dealing with this problem.. Any hints on how to deal with this,
here's the brute force way:

Code:

Code:

#include <iostream>
#include <cmath>
#include <algorithm>
#include <limits>
#include <vector>
#include <bitset>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <time.h>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <cctype>
#include <list>
#include <iterator>
#include <iosfwd>
 
using std::cin;
using std::cout;
 
int main() {
 
    int t;cin>>t;while(t--){  //test cases
        int n;cin>>n; //length of string
        string s;cin>>s; //string input
 
        int max_sub=-1;   //result
        for(int i=0;i<n;i++)
            {
                for(int len=1;len<=n-i;len++)
                {
                    string s1=s.substr(i,len); //get all the sub strings(hence brute force)
                    //cout<<s1<<"\n";
                    map<char,int> m;  //map to find the frequencies
                    for(int j=0;j<s1.length();j++)  //take the substring
                    {
                        m[s1[j]]++;//count the frequency
 
                        int val=s1.length();
                        if(m[s1[j]=]=>=val/2)   // if found any character with freq >= (length of substring)/2 
                            { 
                                if(val>max_sub)  //check if length is greater than prev max value
                                    {max_sub=val;} //update
                            break;//break, since we need atleast one character(so only one chacter will do the job)
                            } 
                    }
 
                }
                
            }
 
            cout<<max_sub<<"\n"; //print the result
    }
 
    return 0;
}

What do you mean "optimizaton needed"? A brute force "solution" isn't a solution in competitive programming at all. A monkey could write that. The whole point is to come up with a clever solution. And since this is from a currently-running contest, you are basically asking for someone to help you cheat. If you can't solve it, you lose. Period. That's what "contest" means.

And what kind of a moron includes 15 unnecessary headers? Are you thinking at all???

BTW, I see someone already helped you to cheat on another site. I'm going to see if I can report you on the contest site.

I see... you have a lot of frustration in your life, and since, you are too much of a coward to deal with them, you go online and try to undermine other's work, cool good for you.. and who says bruteforce approach is not a solution in competitive coding, this just shows me how little you know about competitive coding, a dynamic programming uses bruteforce, every good algorithm arises from bruteforce. It's because of keyboard warriors like you who don't help anyone at all, but try to not get them help from others too. I see your other posts as well, never doing anything productive and just trying to troll on others. good luck mate, it's very easy to be brave online and ........ yourself in real. you don't need to help others if you want, but just shut yourself up, if you don't want to, nobody cares about your opinion anyways.. cheers.

Blah blah blah. What a bunch of bull!!!

I see your account was closed on the other site.
Was that the admin (I doubt it) or was it your own cowardice?

You are a loser, literally.